package com.ztom.top100;

/**
 * 分割等和子集
 * <p>
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 *
 * @author ZhangTao
 */
public class Code87CanPartition {

    public boolean canPartition2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 拆分成两个等和子集, 那么 sum 必须是偶数
        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
        // 如果有元素大于 target 那指定不能分成两个等和子集
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }

        return process(nums, 0, target);
    }

    private boolean process(int[] nums, int i, int rest) {
        if (i == nums.length) {
            return rest == 0;
        }
        if (rest == 0) {
            return true;
        }

        boolean p = process(nums, i + 1, rest);
        if (rest >= nums[i]) {
            p |= process(nums, i + 1, rest - nums[i]);
        }

        return p;
    }

    public boolean canPartition1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 拆分成两个等和子集, 那么 sum 必须是偶数
        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
        // 如果有元素大于 target 那指定不能分成两个等和子集
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }
        int n = nums.length;
        boolean[][] dp = new boolean[n][target + 1];
        dp[0][nums[0]] = true;
        // 第 0 列
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int rest = 1; rest <= target; rest++) {
                if (rest >= nums[i]) {
                    dp[i][rest] = dp[i + 1][rest] | dp[i + 1][rest - nums[i]];
                } else {
                    dp[i][rest] = dp[i + 1][rest];
                }
            }
        }

        return dp[0][target];
    }

    /**
     * 空间压缩
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 拆分成两个等和子集, 那么 sum 必须是偶数
        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
        // 如果有元素大于 target 那指定不能分成两个等和子集
        for (int num : nums) {
            if (num > target) {
                return false;
            }
        }
        int n = nums.length;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int rest = target; rest >= nums[i]; rest--) {
                dp[rest] = dp[rest] | dp[rest - nums[i]];
            }
        }

        return dp[target];
    }
}
